package com.arron.algorithm.leetcodetop100.动态规划.背包问题;


import java.util.List;

/**
 *  回溯穷举 :
 *  @see com.arron.algorithm.leetcodetop100.回溯.零钱兑换II
 *
 */
public class 零钱兑换II {



    public int change(int amount, int[] coins) {
         int n=  coins.length;
        //定义dp ： dp[i][j] 表示前i个硬币凑成 金钱j的方法有多少种
        int[][] dp = new int[n+1][amount +1];

        //base case
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j-coins[i-1] <0){
                    dp[i][j] = dp[i-1][j];
                }else {
                    // 当前第i个硬币 不装入背包的方法 + 装入背包的方法
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }


            }

        }

        return dp[n][amount];
    }




    public static void main(String[] args) {
        零钱兑换II changge = new 零钱兑换II();

        int[] nums = {1,2,5};
        changge.change(5, nums);
    }




}
